import com.sun.source.tree.Tree;

public class BinarySearchTree {
    //关于二叉搜索树的类

    //创建一个关于节点的内部类
    static class TreeNode {
        //节点中有一个数据域，两个指针域
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            //创建节点时，赋初值
            this.val = val;
        }
    }

    TreeNode root;   //创建根节点

    //第一个方法：搜索
    //在二叉搜索树中搜索一个值
    //1：用递归的方法实现此方法
    public TreeNode search(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        //如果根节点值等于目标值
        if (root.val == val) {
            return root;
        } else {
            //如果根节点的值比目标值小，则去右子树中寻找
            if (root.val < val) {
                TreeNode t1 = search(root.right, val);
                return t1;
            } else {
                TreeNode t2 = search(root.left, val);
                return t2;
            }
        }
    }

    /**
     * 时间复杂度为：最好情况：O(logN)
     *   最坏情况：变成单分支树：O(N)
     *   问题：能不能一开始搜索的树即为根节点呢，那最好情况是不是O(1)?
     *
     * @param val
     * @return
     */
    //2:   用遍历相应路径节点的方法：
    //递归起到的作用通常情况下为。为遍历一条路径或多条路径
    //因为我们也可以通过设定条件直接遍历，而不采用递归
    public TreeNode search2(int val) {
        //在类中的方法，可以直接引用类中的字段属性
        //root.val = 10;
        //遍历整个二叉树
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val == val) {
                return root;
            } else if (cur.val > val) {
                //如果根节点值比要查找的值大，则往左子树上寻找
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }
//第二个方法：插入：
      //用于向二叉搜索树中插入元素，或创建二叉搜索树
      //采用非递归的方法
      public void insert(int val){
           TreeNode node  = new TreeNode(val);
           if(root==null){
               root = node;
               return ;
           }
          TreeNode cur = root;
           //设置一个父亲节点
          TreeNode parent = null;
           //如果根节点的值比要插入的值大，则将此值插入到左子树上去。
          while (cur!=null) {
              if (cur.val > val) {
                  parent = cur;
                  cur = cur.left;
              } else if(cur.val>val)    {
                  //如果根节点值比要插入的值小，则将此值插入到右子树上去.
                  parent = cur;
                  cur = cur.right;
              }else {
                  //如果要插入的值在二叉搜索树中已经存在，直接返回
                   return;
              }
          }
        //当cur为空时：需要判断新的节点是插在父母节点的左子树上，还是右子树上
          if(val>parent.val) {
              parent.right = node;
          }else {
              parent.left = node;
          }
      }
//第三个方法：删除
    //在面试时，最多的情况考查找与搜索
    public void remove(int val){
        //要删除一个节点，
        //此节点有三种情况，左子树为空，右子树为空，左右子树均不为空，还有一个特殊情况，左右节点均为空，只有一个根节点
        if(root==null){
            return ;
        }
        //需要先找到此节点的位置
        TreeNode cur  = root;
        TreeNode parent = null;
        while (cur !=null) {
            //如果当前cur指向的值即要删除的值
            if (cur.val == val) {
                  //调用删除函数
                delete(cur,parent);
            } else if(cur.val>val) {
                //如果根节点的值小，则访问右子树
                   parent = cur;
                    cur =cur.right;

            }else{
                   parent = cur;
                   cur = cur.left;
            }
        }
    }
    private void delete(TreeNode cur,TreeNode parent) {
         //当要删除的节点为左树为空时，三种情况：
        if(cur.left ==null){
            //先判断此节点是否为根节点，如果是根节点
            if(cur == root){
                root = root.right;
            }else if(cur==parent.left)  {
                //如果当前节点不是根节点,有两种情况，当前节点是父亲节点的左子树
                parent.left = cur.right;

            }else if(cur ==parent.right){
                   //如果当前节点是父亲节点右子树
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            //先判断此节点是否为根节点，如果是根节点
            if(cur == root){
                root = root.left;
            }else if(cur==parent.left)  {
                //如果当前节点不是根节点,有两种情况，当前节点是父亲节点的左子树
                parent.left = cur.left;
            }else if(cur ==parent.right){
                //如果当前节点是父亲节点右子树
                parent.right = cur.left;
            }
        }else {
            //当左右子树均不为空时
            //采用替换删除法：
            //找到当前节点左子树的最左节点或者当前节点右子树的最右节点
            TreeNode cur2 = cur.left;
            //当左子树只有一个节点呢？
            TreeNode parent2 = cur;
            while (cur2.right!=null){
                parent2 = cur2;
                cur2 = cur2.right;
            }
           //用最左节点的值覆盖掉cur节点的值
             cur.val = cur2.val;
         //    parent2.right = null;   //再删除掉最右节点,
            //最右节点还有可能有左子树啊

           // parent2.right = cur2.left;
            //如果左子树中除去左子树根节点外，其右边没有数据了，
            //那么parent2.left = cur2啊。
            if(parent2.right == cur2){
                parent2.right = cur2.left;
            }else {
                parent2.left = cur2.left;
            }

        }







    }


}








